EVALUACIÓN REVERSIBLE

“La ciencia pretende comprender la realidad con la mínima ideología posible” (Jorge Wagensberg)

“El conocimiento matemático es el conocimiento adquirido por la razón mediante la construcción de conceptos” (Kant)

---

Tipos de evaluaciones y reversibilidad

En MENTAL no hay evaluación o computación reversible completa, pues no se registran en el espacio abstracto los pasos intermedios. Sin embargo, existe un mecanismo de evaluación reversible asociada a la sustitución potencial y al reconocimiento de formas.

El proceso de evaluación es un proceso “hacia adelante” y está asociado a la utilización de expresiones de sustitución de tipo actual o inmediato, por ejemplo,

(a = 3)
(b = 4)
(u = a+b) // ev. 7
(v = a*b) // ev. 12
(x = u+v) // ev. 7+12 ev. 19

También, como hemos visto, puede haber evaluación diferida, por ejemplo,

(a = 3)
(b = 4)
(u = (a+b)°) // ev. (u = a+b)
(v = (a*b°)) // ev. (v = a*b)
(x = u+v) // ev. 7+12 ev. 19

Sin embargo, cuando utilizamos la sustitución potencial, es decir, la representación, la situación cambia, produciéndose el fenómeno de la evaluación reversible, un proceso “hacia atrás”.

El caso más simple es el siguiente:

(x =: a) // x representa a a

x // ev. x (x se autoevalúa pero representa a a)

a // ev. x (a se evalúa como su representante, x)

Realmente hay dos tipos de evaluaciones:

1. Externa. Es la evaluación superficial, aparente, la que aparece externamente.
   
   
2. Interna. Es la evaluación profunda, real, verdadera, la que se utiliza internamente en los cálculos.

Cuando utilizamos la sustitución inmediata, la evaluación interna y externa coinciden.

Cuando en el comentario asociado a una expresión indicamos “ev.”, nos estamos refiriendo a la evaluación externa.

El ejemplo anterior, indicando los dos tipos de evaluación:

(x° =: a) // x representa a a
x // ev. externa: x, ev. interna: a
a // ev. externa: x, ev. interna: a

Otro ejemplo:

(x =: u)
(u =: a)
x // ev. externa: x, ev. interna: a
u // ev. externa: x, ev. interna: a
a // ev. externa: x, ev. interna: a

En el último caso, en la evaluación (externa) de a, hay dos saltos hacia atrás. La evaluación interna de x, u y a es, en los tres casos, la misma: a.


Tipo de sustitución como parámetro

En el siguiente ejemplo, utilizamos un parámetro, p, para indicar el tipo de sustitución que queremos aplicar. Su valor es : o la expresión nula θ.

(x =p u)°
(u =p a)°
(p = θ) // aplicar sustitución actual o inmediata
x // ev. a
u // ev. a
a // ev. a
(p = :°) // aplicar sustitución potencial
x // ev. x
u // ev. x
a // ev. x

Reconocimiento de formas

La sustitución potencial permite reconocer formas, es decir, expresiones particulares correspondientes a expresiones genéricas. Ejemplos:

1. ⟨( f(x y) =: (x+y x*y) )⟩
(a+b a*b) // ev. f(a b) (reconoce la forma)
(7 12) // se autoevalúa (no es posible, en este caso, ir hacia atrás)
   
   
2. ⟨( g(x) =: (x xx xxx) )⟩
(1 11 111) // ev. g(1)
(a aa aaa) // ev. g(a)
(ab (ab ab) (ab ab ab)) // ev. g(ab)

Tiene que haber una sustitución potencial directa (parametrizada o no) y no un proceso. Por ejemplo, la secuencia (a a a a) no se evalúa como a★4 porque la definición de repetición se realiza mediante una función recursiva.

---

Adenda
La computación reversible

La teoría de la computación reversible surgió en IBM a comienzos de de la década de de los años 1960´s. Desde entonces se sigue investigando.

En la práctica, la implementación de la computación reversible en un microprocesador tiene inconvenientes:

• Es una tarea compleja, pues requiere una profunda modificación del diseño del procesador.
• El rendimiento es menor. Para paliarlo, habría que incrementar en gran medida el proceso en paralelo.
• Requiere mayor cantidad de memoria.

Pero también tiene ventajas:

• Se amplían las posibilidades de computación.
• Se pueden reutilizar los cálculos intermedios.
• Se reduce el consumo, pues permite recapturar la energía utilizada en un cálculo y reutilizarlo en el próximo, con la consiguiente menor disipación de calor. Es por ello que la computación reversible se denomina también “computación adiabática”.

La única empresa que, hasta el momento, ha diseñado un procesador reversible es Adiabatic Logic.


Bibliografía

• Bennet, Charles H. Logical Reversibility of Computation. IBM Journal of Research and Development, 17, 525, 1973.
  
  
• Bennet, Charles H. Notes on the History of Reversible Computation. IBM Journal of Research and Development, 32 (1), 16, 1988.
  
  
• Feynman, Richard P. Computación reversible y la termodinámica de la computación. Capítulo 5 de Conferencias sobre Computación. Crítica, Barcelona, 2003.